//
// Created by xili on 2024/10/11 10:21.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root) {
        int diameter = 0;
        dfs(root, diameter);  // 深度优先搜索并更新直径
        return diameter;
    }

    int dfs(TreeNode *root, int &diameter) {
        if (!root) {
            return 0;  // 空节点的深度为0
        }

        // 递归计算左右子树的深度
        int leftDepth = dfs(root->left, diameter);
        int rightDepth = dfs(root->right, diameter);

        // 更新直径，路径长度为左右子树的深度和
        diameter = max(diameter, leftDepth + rightDepth);

        // 返回当前节点的深度
        return 1 + max(leftDepth, rightDepth);
    }
};
